package com.gxc.array;

/**
 * 1186. 删除一次得到子数组最大和
 给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
 换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），
 （删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

 注意，删除一个元素后，子数组 不能为空
 */
public class MaximumSum {

    public static void main(String[] args) {
        System.out.println(handle(new int[]{1,-2,0,3}));
        //System.out.println(handle(new int[]{1,-2,-2,3}));
        //System.out.println(handle(new int[]{-1,-1,-1,-1}));
    }

    /**
     * dp[i][0]=max(dp[i−1][0],0)+arr[i]
     dp[i][1]=max(dp[i−1][1]+arr[i],dp[i−1][0])

     * @param arr
     * @return
     */
    public static int handle(int[] arr) {
        int dp0 = arr[0], dp1 = 0, max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            //得先算dp1，因为dp1 的计算结果需要dp0
            dp1 = Math.max(dp1 + arr[i], dp0);
            dp0 = Math.max(dp0, 0) + arr[i];
            max = Math.max(max, Math.max(dp0, dp1));
        }
        return max;
    }

    class Solution {
        public int maximumSum(int[] arr) {
            int dp0 = arr[0], dp1 = 0, res = arr[0];
            for (int i = 1; i < arr.length; i++) {
                dp1 = Math.max(dp0, dp1 + arr[i]);
                dp0 = Math.max(dp0, 0) + arr[i];
                res = Math.max(res, Math.max(dp0, dp1));
            }
            return res;
        }
    }

}
